{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #除法求值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph #array #shortest-path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图 #数组 #最短路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: calcEquation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #除法求值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个变量对数组 <code>equations</code> 和一个实数值数组 <code>values</code> 作为已知条件，其中 <code>equations[i] = [A<sub>i</sub>, B<sub>i</sub>]</code> 和 <code>values[i]</code> 共同表示等式 <code>A<sub>i</sub> / B<sub>i</sub> = values[i]</code> 。每个 <code>A<sub>i</sub></code> 或 <code>B<sub>i</sub></code> 是一个表示单个变量的字符串。</p>\n",
    "\n",
    "<p>另有一些以数组 <code>queries</code> 表示的问题，其中 <code>queries[j] = [C<sub>j</sub>, D<sub>j</sub>]</code> 表示第 <code>j</code> 个问题，请你根据已知条件找出 <code>C<sub>j</sub> / D<sub>j</sub> = ?</code> 的结果作为答案。</p>\n",
    "\n",
    "<p>返回 <strong>所有问题的答案</strong> 。如果存在某个无法确定的答案，则用 <code>-1.0</code> 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 <code>-1.0</code> 替代这个答案。</p>\n",
    "\n",
    "<p><strong>注意：</strong>输入总是有效的。可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>equations = [[&quot;a&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;c&quot;]], values = [2.0,3.0], queries = [[&quot;a&quot;,&quot;c&quot;],[&quot;b&quot;,&quot;a&quot;],[&quot;a&quot;,&quot;e&quot;],[&quot;a&quot;,&quot;a&quot;],[&quot;x&quot;,&quot;x&quot;]]\n",
    "<strong>输出：</strong>[6.00000,0.50000,-1.00000,1.00000,-1.00000]\n",
    "<strong>解释：</strong>\n",
    "条件：<em>a / b = 2.0</em>, <em>b / c = 3.0</em>\n",
    "问题：<em>a / c = ?</em>, <em>b / a = ?</em>, <em>a / e = ?</em>, <em>a / a = ?</em>, <em>x / x = ?</em>\n",
    "结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>equations = [[&quot;a&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;c&quot;],[&quot;bc&quot;,&quot;cd&quot;]], values = [1.5,2.5,5.0], queries = [[&quot;a&quot;,&quot;c&quot;],[&quot;c&quot;,&quot;b&quot;],[&quot;bc&quot;,&quot;cd&quot;],[&quot;cd&quot;,&quot;bc&quot;]]\n",
    "<strong>输出：</strong>[3.75000,0.40000,5.00000,0.20000]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>equations = [[&quot;a&quot;,&quot;b&quot;]], values = [0.5], queries = [[&quot;a&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;a&quot;],[&quot;a&quot;,&quot;c&quot;],[&quot;x&quot;,&quot;y&quot;]]\n",
    "<strong>输出：</strong>[0.50000,2.00000,-1.00000,-1.00000]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= equations.length &lt;= 20</code></li>\n",
    "\t<li><code>equations[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= A<sub>i</sub>.length, B<sub>i</sub>.length &lt;= 5</code></li>\n",
    "\t<li><code>values.length == equations.length</code></li>\n",
    "\t<li><code>0.0 &lt; values[i] &lt;= 20.0</code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 20</code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= C<sub>j</sub>.length, D<sub>j</sub>.length &lt;= 5</code></li>\n",
    "\t<li><code>A<sub>i</sub>, B<sub>i</sub>, C<sub>j</sub>, D<sub>j</sub></code> 由小写英文字母与数字组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 399&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/evaluate-division/\">https://leetcode-cn.com/problems/evaluate-division/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [vlzXQL](https://leetcode.cn/problems/vlzXQL/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [vlzXQL](https://leetcode.cn/problems/vlzXQL/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"a\",\"b\"],[\"b\",\"c\"]]\\n[2.0,3.0]\\n[[\"a\",\"c\"],[\"b\",\"a\"],[\"a\",\"e\"],[\"a\",\"a\"],[\"x\",\"x\"]]', '[[\"a\",\"b\"],[\"b\",\"c\"],[\"bc\",\"cd\"]]\\n[1.5,2.5,5.0]\\n[[\"a\",\"c\"],[\"c\",\"b\"],[\"bc\",\"cd\"],[\"cd\",\"bc\"]]', '[[\"a\",\"b\"]]\\n[0.5]\\n[[\"a\",\"b\"],[\"b\",\"a\"],[\"a\",\"c\"],[\"x\",\"y\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        # 构建图\n",
    "        graph = defaultdict(dict)\n",
    "        for (a, b), val in zip(equations, values):\n",
    "            graph[a][b] = val\n",
    "            graph[b][a] = 1 / val\n",
    "\n",
    "        # 深度优先搜索\n",
    "        def dfs(start, end, visited):\n",
    "            if start not in graph or end not in graph:\n",
    "                return -1.0\n",
    "            if start == end:\n",
    "                return 1.0\n",
    "            visited.add(start)\n",
    "            for neighbor in graph[start]:\n",
    "                if neighbor not in visited:\n",
    "                    result = dfs(neighbor, end, visited)\n",
    "                    if result != -1.0:\n",
    "                        return result * graph[start][neighbor]\n",
    "            return -1.0\n",
    "\n",
    "        # 处理查询\n",
    "        results = []\n",
    "        for query in queries:\n",
    "            start, end = query\n",
    "            visited = set()\n",
    "            result = dfs(start, end, visited)\n",
    "            results.append(result)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, name: str):\n",
    "        self.name = name\n",
    "        self.neiborhoods_weight = dict()\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        self.name_nodes = dict()\n",
    "        for equation, value in zip(equations, values):\n",
    "            name1, name2 = equation\n",
    "            if name1 not in self.name_nodes.keys():\n",
    "                self.name_nodes[name1] = Node(name1)\n",
    "            if name2 not in self.name_nodes.keys():\n",
    "                self.name_nodes[name2] = Node(name2)\n",
    "            if name2 not in self.name_nodes[name1].neiborhoods_weight.keys():\n",
    "                self.name_nodes[name1].neiborhoods_weight[name2] = value\n",
    "            if name1 not in self.name_nodes[name2].neiborhoods_weight.keys():\n",
    "                self.name_nodes[name2].neiborhoods_weight[name1] = 1.0 / value\n",
    "        \n",
    "        for_return = []\n",
    "        for query in queries:\n",
    "            name1, name2 = query\n",
    "            value, flag = self.search_path(name1, name2, [name1])\n",
    "            for_return.append(value)\n",
    "        return for_return\n",
    "    \n",
    "    def search_path(self, name1, name2, path):\n",
    "        if name1 not in self.name_nodes.keys():\n",
    "            return -1.0, False\n",
    "        if name2 not in self.name_nodes.keys():\n",
    "            return -1.0, False\n",
    "        if name1 == name2:\n",
    "            return 1.0, True\n",
    "\n",
    "        if name2 in self.name_nodes[name1].neiborhoods_weight.keys():\n",
    "            return self.name_nodes[name1].neiborhoods_weight[name2], True\n",
    "        else:\n",
    "            for key in self.name_nodes[name1].neiborhoods_weight.keys():\n",
    "                if  key not in path:\n",
    "                    value , flag = self.search_path(key, name2, path + [key])\n",
    "                    if flag:\n",
    "                        return value * self.name_nodes[name1].neiborhoods_weight[key], True\n",
    "                    else:\n",
    "                        continue\n",
    "\n",
    "        return -1.0, False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = {}\n",
    "        for (a, b), v in zip(equations, values):\n",
    "            if a not in graph:\n",
    "                graph[a] = {b: v}\n",
    "            else:\n",
    "                graph[a][b] = v\n",
    "            if b not in graph:\n",
    "                graph[b] = {a: 1/v}\n",
    "            else:\n",
    "                graph[b][a] = 1/v\n",
    "        def dfs(s, t):\n",
    "            if s not in graph:\n",
    "                return -1.0\n",
    "            if s == t:\n",
    "                return 1.0\n",
    "            used.add(s)\n",
    "            for k in graph[s]:\n",
    "                if k == t:\n",
    "                    return graph[s][k]\n",
    "                elif k not in used:\n",
    "                    v = dfs(k, t)\n",
    "                    if v != -1.0:\n",
    "                        return v * graph[s][k]\n",
    "            return -1.0\n",
    "        res = []\n",
    "        for qs, qt in queries:\n",
    "            used = set()\n",
    "            res.append(dfs(qs, qt))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        # 构建图\n",
    "        graph = defaultdict(dict)\n",
    "        for (a, b), val in zip(equations, values):\n",
    "            graph[a][b] = val\n",
    "            graph[b][a] = 1 / val\n",
    "\n",
    "        # 深度优先搜索\n",
    "        def dfs(start, end, visited):\n",
    "            if start not in graph or end not in graph:\n",
    "                return -1.0\n",
    "            if start == end:\n",
    "                return 1.0\n",
    "            visited.add(start)\n",
    "            for neighbor in graph[start]:\n",
    "                if neighbor not in visited:\n",
    "                    result = dfs(neighbor, end, visited)\n",
    "                    if result != -1.0:\n",
    "                        return result * graph[start][neighbor]\n",
    "            return -1.0\n",
    "\n",
    "        # 处理查询\n",
    "        results = []\n",
    "        for query in queries:\n",
    "            start, end = query\n",
    "            visited = set()\n",
    "            result = dfs(start, end, visited)\n",
    "            results.append(result)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        from collections import defaultdict\n",
    "        conditions = defaultdict(lambda:{})\n",
    "\n",
    "        for (a,b),v in zip(equations, values):\n",
    "            conditions[a][b] = v\n",
    "            conditions[b][b] = 1.\n",
    "            if v != 0:\n",
    "                conditions[b][a] = 1. / v\n",
    "                conditions[a][a] = 1.\n",
    "        \n",
    "        from collections import deque\n",
    "        \n",
    "        ret = []\n",
    "        for c,d in queries:\n",
    "            if c not in conditions or d not in conditions:\n",
    "                ret.append(-1.)\n",
    "                continue\n",
    "            \n",
    "            if c == d:\n",
    "                if d in conditions[c]:\n",
    "                    ret.append(1.)\n",
    "                else:\n",
    "                    ret.append(-1.)\n",
    "                continue\n",
    "\n",
    "            queue = deque()\n",
    "            queue.append((c,1.))\n",
    "            visited = set()\n",
    "            visited.add(c)\n",
    "\n",
    "            found = False\n",
    "            while len(queue) > 0:\n",
    "                var, val = queue.popleft()\n",
    "                if var == d:\n",
    "                    ret.append(val)\n",
    "                    found = True\n",
    "                    break\n",
    "                \n",
    "                for nei in conditions[var]:\n",
    "                    if nei not in visited:\n",
    "                        visited.add(nei)\n",
    "                        queue.append((nei, val*conditions[var][nei]))\n",
    "\n",
    "            if not found:\n",
    "                ret.append(-1.)\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        dic = {}\n",
    "        graph = DefaultDict(set)\n",
    "        for (a, b), v in zip(equations, values):\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "            dic[(a, b)] = v\n",
    "            dic[(b, a)] = 1 / v\n",
    "        res = []\n",
    "        for a, b in queries:\n",
    "            if a not in graph or b not in graph:\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                visited = set()\n",
    "                visited.add(a)\n",
    "                queue = deque([(a, 1)])\n",
    "                cur = -1\n",
    "                while queue:\n",
    "                    l, v = queue.popleft()\n",
    "                    if l == b:\n",
    "                        cur = v\n",
    "                        break\n",
    "                    for r in graph[l]:\n",
    "                        if r not in visited:\n",
    "                            visited.add(r)\n",
    "                            queue.append((r, v * dic[(l, r)]))\n",
    "                res.append(cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = {}\n",
    "        for (x,y),v in zip(equations,values):\n",
    "            if x in graph:\n",
    "                graph[x][y] = v\n",
    "            else:\n",
    "                graph[x] = {y:v}\n",
    "            if y in graph:\n",
    "                graph[y][x] = 1/v\n",
    "            else:\n",
    "                graph[y] = {x:1/v}\n",
    "        \n",
    "        def dfs(s,t):\n",
    "            if s not in graph:\n",
    "                return -1\n",
    "            if t == s:\n",
    "                return 1\n",
    "            for node in graph[s].keys():\n",
    "                if node == t:\n",
    "                    return graph[s][node]\n",
    "                \n",
    "                elif node not in visited:\n",
    "                    visited.add(node)\n",
    "                    v = dfs(node,t)\n",
    "                    if v != -1:\n",
    "                        return graph[s][node] * v\n",
    "            \n",
    "            return -1\n",
    "        \n",
    "        res = []\n",
    "        for qs,qt in queries:\n",
    "            visited = set()\n",
    "            res.append(dfs(qs,qt))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        edges = collections.defaultdict(dict)\n",
    "        for v, (a, b) in zip(values, equations):\n",
    "            edges[a][b] = v\n",
    "            edges[b][a] = 1/v\n",
    "        \n",
    "        def dfs(source, target, vis):\n",
    "            if source == target:\n",
    "                return 1.0, True\n",
    "        \n",
    "            for b, v in edges[source].items():\n",
    "                if b not in vis:\n",
    "                    vis.add(b)\n",
    "                    u, f = dfs(b, target, vis)\n",
    "                    if f:\n",
    "                        return v*u, True\n",
    "            \n",
    "            return -1.0, False\n",
    "            \n",
    "        answers = []\n",
    "        for a, b in queries:\n",
    "            if a not in edges or b not in edges:\n",
    "                answers.append(-1.0)\n",
    "            else:\n",
    "                u, _ = dfs(a, b, set([a]))\n",
    "                answers.append(u)\n",
    "        \n",
    "        return answers\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = {}\n",
    "        for i, (a, b) in enumerate(equations):\n",
    "            if a not in graph:\n",
    "                graph[a] = []\n",
    "            if b not in graph:\n",
    "                graph[b] = []\n",
    "            graph[a].append((b, values[i]))\n",
    "            graph[b].append((a, 1/values[i]))\n",
    "        \n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            if a not in graph or b not in graph:\n",
    "                ans.append(-1)\n",
    "                continue\n",
    "            if a == b:\n",
    "                ans.append(1)\n",
    "                continue\n",
    "            visited = {a}\n",
    "            q = [(a, 1)]\n",
    "            flag = False\n",
    "            while q:\n",
    "                nxt = []\n",
    "                for x, cur_val in q:\n",
    "                    for node, val in graph[x]:\n",
    "                        if node == b:\n",
    "                            ans.append(cur_val*val)\n",
    "                            flag = True\n",
    "                            break\n",
    "                        elif node not in visited:\n",
    "                            visited.add(node)\n",
    "                            nxt.append((node, cur_val*val))\n",
    "                    if flag:\n",
    "                        break\n",
    "                if flag:\n",
    "                    break\n",
    "                q = nxt\n",
    "            if not flag:\n",
    "                ans.append(-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = {}\n",
    "        for (a, b), v in zip(equations, values):\n",
    "            if a not in graph:\n",
    "                graph[a] = {b: v}\n",
    "            else:\n",
    "                graph[a][b] = v\n",
    "            if b not in graph:\n",
    "                graph[b] = {a: 1/v}\n",
    "            else:\n",
    "                graph[b][a] = 1/v\n",
    "        def dfs(s, t):\n",
    "            if s not in graph:\n",
    "                return -1.0\n",
    "            if s == t:\n",
    "                return 1.0\n",
    "            used.add(s)\n",
    "            for k in graph[s]:\n",
    "                if k == t:\n",
    "                    return graph[s][k]\n",
    "                if k not in used:\n",
    "                    v = dfs(k, t)\n",
    "                    if v != -1.0:\n",
    "                        return v * dfs(s, k)\n",
    "            return -1.0\n",
    "        res = []\n",
    "        for qs, qt in queries:\n",
    "            used = set()\n",
    "            res.append(dfs(qs, qt))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        neighbors = defaultdict(set)\n",
    "        results = defaultdict(dict)\n",
    "        n = len(equations)\n",
    "        for i in range(n):\n",
    "            equ = equations[i]\n",
    "            a,b = equ[0],equ[1]\n",
    "            neighbors[a].add(b)\n",
    "            neighbors[b].add(a)\n",
    "            results[a][b] = values[i]\n",
    "            results[b][a] = 1 / values[i]\n",
    "        \n",
    "        def bfs(x,y):\n",
    "            if x not in neighbors:\n",
    "                return -1.0\n",
    "            q = deque([(x,1)])\n",
    "            seen = set()\n",
    "            while q:\n",
    "                node,value = q.popleft()\n",
    "                if node == y:\n",
    "                    return value\n",
    "                for x in neighbors[node]:\n",
    "                    if x not in seen:\n",
    "                        q.append((x,value * results[node][x]))\n",
    "                        seen.add(x)\n",
    "            return -1.0\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(bfs(q[0],q[1]))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        dic1,vis={},{}\n",
    "        def dic_add(k,v,val):\n",
    "            if k not in dic1:\n",
    "                dic1[k]=[[v,val]]\n",
    "            else:\n",
    "                dic1[k].append([v,val])\n",
    "        for idx,(f,t) in enumerate(equations) :\n",
    "            dic_add(f,t,values[idx])\n",
    "            dic_add(t,f,1/values[idx])\n",
    "            vis[t]=False\n",
    "            vis[f]=False\n",
    "        res=[]\n",
    "        def dfs(f,t,cur_v):\n",
    "            if f not in dic1:return -1\n",
    "            if f==t:return cur_v\n",
    "            for i,val in dic1[f]:\n",
    "                if not vis[i]:\n",
    "                    vis[i]=True\n",
    "                    ans=dfs(i,t,cur_v*val)\n",
    "                    vis[i]=False    \n",
    "                    if ans is not None and ans>0:\n",
    "                        return ans \n",
    "        for idx,(f,t) in enumerate(queries):\n",
    "            vis[f]=True\n",
    "            res.append(ans if (ans:=dfs(f,t,1)) is not None else -1)\n",
    "            vis[f]=False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        '''\n",
    "        转换为图(字典存储) + DFS\n",
    "        '''\n",
    "        graph = dict()\n",
    "        for idx, eq in enumerate(equations):\n",
    "            for i in range(2):\n",
    "                if eq[i] not in graph:\n",
    "                    graph[eq[i]] = {eq[~i]: values[idx] if i == 0 else 1 / values[idx]}\n",
    "                else:\n",
    "                    graph[eq[i]][eq[~i]] = values[idx] if i == 0 else 1 / values[idx]\n",
    "        # print(graph)\n",
    "        result = []\n",
    "        for i, ques in enumerate(queries):\n",
    "            var1, var2 = ques[0], ques[1]\n",
    "            if var1 not in graph or var2 not in graph:\n",
    "                result.append(-1.0)\n",
    "                continue\n",
    "            if var1 == var2:\n",
    "                result.append(1.0)\n",
    "                continue\n",
    "            # ans = 1\n",
    "            # dfs\n",
    "            stack = [(var1, 1)]\n",
    "            visited = set([var1])\n",
    "            while stack:\n",
    "                node, ans = stack.pop()\n",
    "                for neigh, val in graph[node].items():\n",
    "                    if neigh not in visited:\n",
    "                        if neigh == var2:\n",
    "                            result.append(ans * val)\n",
    "                            stack = []\n",
    "                            break\n",
    "                        else:\n",
    "                            stack.append((neigh, ans * val))\n",
    "                            visited.add(neigh)\n",
    "            if len(result) == i:\n",
    "                result.append(-1)\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Dict, Tuple\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cache = {}\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = defaultdict(dict)\n",
    "        for i in range(len(equations)):\n",
    "            graph[equations[i][0]][equations[i][1]] = values[i]\n",
    "            graph[equations[i][1]][equations[i][0]] = 1 / values[i]\n",
    "        ans = []\n",
    "        for i in range(len(queries)):\n",
    "            if queries[i][0] not in graph or queries[i][1] not in graph:\n",
    "                ans.append(-1.0)\n",
    "            else:\n",
    "                cost = self.dfs(graph, queries[i][0], queries[i][1], 1.0, set())\n",
    "                ans.append(cost)\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, graph: Dict[str, Dict[str, float]], start: str, end: str, cost: float, used: set):\n",
    "        if start == end:\n",
    "            return cost\n",
    "        for k, v in graph[start].items():\n",
    "            if k not in used:\n",
    "                used.add(k)\n",
    "                val = self.dfs(graph, k, end, cost * v, used)\n",
    "                if val != -1:\n",
    "                    return val\n",
    "                used.discard(k)\n",
    "        return -1.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "\n",
    "        graph = defaultdict(int)\n",
    "        set1 = set()\n",
    "        for i in range(len(equations)):\n",
    "            a, b = equations[i]\n",
    "            graph[(a, b)] = values[i]\n",
    "            graph[(b, a)] = 1/values[i]\n",
    "            set1.add(a)\n",
    "            set1.add(b)\n",
    "\n",
    "         # Floyd算法 求图中任意2点距离\n",
    "        arr = list(set1)\n",
    "        for k in arr:\n",
    "            for i in arr:\n",
    "                for j in arr:\n",
    "                    if graph[(i, k)] and graph[(k, j)]:\n",
    "                        graph[(i, j)] = graph[(i, k)] * graph[(k, j)]\n",
    "\n",
    "        res = []\n",
    "        for x, y in queries:\n",
    "            if graph[(x, y)]:\n",
    "                res.append(graph[(x, y)])\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind():\n",
    "    def __init__(self):\n",
    "        self.fathers = {}\n",
    "        self.values = {}\n",
    "\n",
    "    def add(self, x):\n",
    "        if x not in self.fathers:\n",
    "            self.fathers[x] = None\n",
    "            self.values[x] = 1.0\n",
    "    \n",
    "    def merge(self, x, y, val):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.fathers[root_x] = root_y\n",
    "            self.values[root_x] = val * self.values[y] / self.values[x]\n",
    "\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        base = 1.0\n",
    "        while(self.fathers[root] != None):\n",
    "            root = self.fathers[root]\n",
    "            base *= self.values[root]\n",
    "\n",
    "        while(root != x):\n",
    "            cur_father = self.fathers[x]\n",
    "            self.values[x] *= base\n",
    "            base /= self.values[cur_father]\n",
    "            self.fathers[x] = root\n",
    "            x = cur_father\n",
    "        \n",
    "        return root\n",
    "            \n",
    "    def isConnected(self, x, y):\n",
    "        return x in self.values and y in self.values and self.find(x) == self.find(y)\n",
    "        \n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        uf = UnionFind()\n",
    "        for eq, va in zip (equations, values):\n",
    "            uf.add(eq[0])\n",
    "            uf.add(eq[1])\n",
    "            uf.merge(eq[0], eq[1], va)\n",
    "\n",
    "        ans = [-1.0] * len(queries)\n",
    "        for idx, qu in enumerate(queries):\n",
    "            if uf.isConnected(qu[0], qu[1]):\n",
    "                ans[idx] = uf.values[qu[0]] / uf.values[qu[1]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = defaultdict(list)\n",
    "        n = len(values)\n",
    "        for i in range(n):\n",
    "            graph[equations[i][0]].append((equations[i][1], values[i]))\n",
    "            graph[equations[i][1]].append((equations[i][0], 1/values[i]))\n",
    "        res = [-1.0] * len(queries)\n",
    "        for i, x in enumerate(queries):\n",
    "            start = x[0]\n",
    "            end = x[1]\n",
    "            if start not in graph or end not in graph:\n",
    "                continue\n",
    "            q = deque([(start, 1)])\n",
    "            visited = set([start])\n",
    "            while q:\n",
    "                cur, prod = q.popleft()\n",
    "                for node, value in graph[cur]:\n",
    "                    if node == end:\n",
    "                        res[i] = prod * value\n",
    "                        break\n",
    "                    if node not in visited:\n",
    "                        visited.add(node)\n",
    "                        q.append((node, prod*value))\n",
    "                if res[i] != -1:\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = {}\n",
    "        for (a, b), v in zip(equations, values):\n",
    "            if a not in graph:\n",
    "                graph[a] = {b: v}\n",
    "            else:\n",
    "                graph[a][b] = v\n",
    "            if b not in graph:\n",
    "                graph[b] = {a: 1/v}\n",
    "            else:\n",
    "                graph[b][a] = 1/v\n",
    "        def dfs(s, t):\n",
    "            if s not in graph:\n",
    "                return -1.0\n",
    "            if s == t:\n",
    "                return 1.0\n",
    "            used.add(s)\n",
    "            for k in graph[s]:\n",
    "                if k == t:\n",
    "                    return graph[s][k]\n",
    "                elif k not in used:\n",
    "                    v = dfs(k, t)\n",
    "                    if v != -1.0:\n",
    "                        return v * graph[s][k]\n",
    "            return -1.0\n",
    "        res = []\n",
    "        for qs, qt in queries:\n",
    "            used = set()\n",
    "            res.append(dfs(qs, qt))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        dic1,vis={},{}\n",
    "        def dic_add(k,v,val):\n",
    "            if k not in dic1:\n",
    "                dic1[k]=[[v,val]]\n",
    "            else:\n",
    "                dic1[k].append([v,val])\n",
    "        for idx,(f,t) in enumerate(equations) :\n",
    "            dic_add(f,t,values[idx])\n",
    "            dic_add(t,f,1/values[idx])\n",
    "            vis[t]=False\n",
    "            vis[f]=False\n",
    "        res=[]\n",
    "        def dfs(f,t,cur_v):\n",
    "            if f not in dic1:return -1\n",
    "            if f==t:return cur_v\n",
    "            for i,val in dic1[f]:\n",
    "                if not vis[i]:\n",
    "                    vis[i]=True\n",
    "                    ans=dfs(i,t,cur_v*val)\n",
    "                    vis[i]=False    \n",
    "                    if ans is not None and ans>0:\n",
    "                        return ans \n",
    "        for idx,(f,t) in enumerate(queries):\n",
    "            if t not in dic1:\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            vis[f]=True\n",
    "            res.append(ans if (ans:=dfs(f,t,1)) is not None else -1)\n",
    "            vis[f]=False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        # def cal(pre, start, end, mul):\n",
    "        #     for e in equation_dict[start]:\n",
    "        #         if e[0] in pre:\n",
    "        #             continue \n",
    "        #         if e[0] == end:\n",
    "        #             return mul * e[1]\n",
    "        #         pre.add(start)\n",
    "        #         temp = cal(pre, e[0], end, mul*e[1])\n",
    "        #         pre.remove(start)\n",
    "        #         if temp != -1:\n",
    "        #             return temp\n",
    "        #     return -1 \n",
    "\n",
    "        # equation_dict = defaultdict(list)\n",
    "        # for e, v in zip(equations, values):\n",
    "        #     equation_dict[e[0]].append((e[1], v))\n",
    "        #     equation_dict[e[1]].append((e[0], 1/v))\n",
    "        # res = []\n",
    "        # for q in queries:\n",
    "        #     if q[0] == q[1] and q[1] in equation_dict:\n",
    "        #         res.append(1)\n",
    "        #     else:\n",
    "        #         res.append(cal(set(), q[0], q[1], 1))\n",
    "        # return res \n",
    "\n",
    "        # ------------------------------------\n",
    "        def findAnswer(start, end, mul):\n",
    "            if start not in graph:\n",
    "                return -1.0\n",
    "            for i in graph[start]:\n",
    "                if i == end:\n",
    "                    return graph[start][i] * mul\n",
    "                if i in seen:\n",
    "                    continue\n",
    "                seen.add(i)\n",
    "                flag = findAnswer(i, end, mul*graph[start][i])\n",
    "                if flag != -1.0:\n",
    "                    return flag\n",
    "                seen.remove(i)\n",
    "            return -1.0\n",
    "        \n",
    "        graph = defaultdict(dict)\n",
    "        ch2val = {}\n",
    "        for i, e in enumerate(equations):\n",
    "            a, b = e\n",
    "            graph[a][b] = values[i]\n",
    "            graph[b][a] = 1 / values[i]\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            seen = set()\n",
    "            seen.add(q[0])\n",
    "            res.append(findAnswer(q[0], q[1], 1.0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        g = defaultdict(int)\n",
    "        _set = set()\n",
    "        for [a,b],v in zip(equations,values):\n",
    "            g[(a,b)] = v\n",
    "            g[(b,a)] = 1 / v\n",
    "            _set.add(a)\n",
    "            _set.add(b)\n",
    "        \n",
    "        arr = list(_set)\n",
    "        for k in arr:\n",
    "            for i in arr:\n",
    "                for j in arr:\n",
    "                    if g[(i,k)] and g[(k,j)]:\n",
    "                        g[(i,j)] = g[(i,k)]*g[(k,j)]\n",
    "        ans = []\n",
    "        for a,b in queries:\n",
    "            if g[(a,b)]:\n",
    "                ans.append(g[(a,b)])\n",
    "            else:\n",
    "                ans.append(-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        g = defaultdict(list)\n",
    "        for (u, v), w in zip(equations, values):\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, 1 / w))\n",
    "\n",
    "        def dfs(u, cur, end, i):\n",
    "            vis.add(u)\n",
    "            if u == end:\n",
    "                ans[i] = cur\n",
    "                return\n",
    "            for v, w in g[u]:\n",
    "                if v not in vis:\n",
    "                    dfs(v, cur * w, end, i)\n",
    "\n",
    "        ans = [-1.0] * len(queries)\n",
    "        for i, (u, v) in enumerate(queries):\n",
    "            if u in g and v in g:\n",
    "                vis = set()\n",
    "                dfs(u, 1.0, v, i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        dic = {}\n",
    "        for i in range(len(equations)):\n",
    "            e = equations[i]\n",
    "            dic[(e[0], e[1])] = values[i]\n",
    "            dic[(e[1], e[0])]  =1 / values[i]\n",
    "        visited = set()\n",
    "        def dfs(x, y):\n",
    "            if x not in list(x[0] for x in dic):\n",
    "                return -1.0\n",
    "            elif (x, y) in dic:\n",
    "                return dic[(x, y)]\n",
    "            else:\n",
    "                visited.add(x)\n",
    "                ans = 0\n",
    "                for k in dic:\n",
    "                    if k[0] == x and k[1] not in visited:\n",
    "                        ans = dic[(x, k[1])]\n",
    "                        temp = dfs(k[1], y)\n",
    "                        if temp != -1.0:\n",
    "                            return ans * temp\n",
    "                return -1.0\n",
    "        \n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            visited = set()\n",
    "            ans.append(dfs(q[0], q[1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        dic = {}\n",
    "        ans = []\n",
    "        nexts = {}\n",
    "        deque = collections.deque()\n",
    "        for i, j in zip(equations, values):\n",
    "            i1 = i[0]\n",
    "            i2 = i[1]\n",
    "            dic[(i1,i2)] = j\n",
    "            if i1 not in nexts:\n",
    "                nexts[i1] = set()\n",
    "            nexts[i1].add(i2)\n",
    "            dic[(i2,i1)] = 1/j\n",
    "            if i2 not in nexts:\n",
    "                nexts[i2] = set()\n",
    "            nexts[i2].add(i1)\n",
    "        for q in queries:\n",
    "            q1 = q[0]\n",
    "            q2 = q[1]\n",
    "            if (q1, q2) in dic:\n",
    "                ans.append(dic[(q1, q2)])\n",
    "                continue\n",
    "            elif q1 not in nexts or q2 not in nexts:\n",
    "                ans.append(-1)\n",
    "                continue\n",
    "            deque = collections.deque()\n",
    "            deque.append((q1, 1))\n",
    "            visit = set()\n",
    "            visit.add(q1)\n",
    "            flag = True\n",
    "            while deque:\n",
    "                cur = deque.popleft()\n",
    "                if cur[0] == q[1]:\n",
    "                    ans.append(cur[1])\n",
    "                    dic[(q1, q2)] = cur[1]\n",
    "                    dic[(q2, q1)] = 1/cur[1]\n",
    "                    flag = False\n",
    "                    break\n",
    "                \n",
    "                for next in nexts[cur[0]]:\n",
    "                    if next not in visit:\n",
    "                        visit.add(next)\n",
    "                        deque.append((next, cur[1]*dic[(cur[0], next)]))\n",
    "            if flag:\n",
    "                ans.append(-1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        valueList = dict()\n",
    "        g = defaultdict(list)\n",
    "        for (i,j), v in zip(equations, values):\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "            # if (i, j) not in values:\n",
    "            #     values[(i,j)] = [v]\n",
    "            # else:\n",
    "            valueList[(i,j)] = v\n",
    "            # if ()\n",
    "            valueList[(j, i)] = 1 / v\n",
    "        \n",
    "        def dfs(i, j, load, tmp, visited):\n",
    "            if i == j:\n",
    "                load.append(tmp)\n",
    "                return\n",
    "            for y in g[i]:\n",
    "                if y not in visited:\n",
    "                    visited.append(y)\n",
    "                    dfs(y, j, load, tmp * valueList[(i, y)], visited)\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            x, y = q[0], q[1]\n",
    "            if x not in g or y not in g:\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                # load = [-1]\n",
    "                # dfs(x, y, load, 1.0, [x])\n",
    "                # if len(load) > 0:\n",
    "                #     res.append(load[1])\n",
    "                visited = set()\n",
    "                visited.add(x)\n",
    "                q = deque([(x, 1)])\n",
    "                cur = -1\n",
    "                while q:\n",
    "                    i, v = q.popleft()\n",
    "                    if i == y:\n",
    "                        cur = v\n",
    "                        break\n",
    "                    for j in g[i]:\n",
    "                        if j not in visited:\n",
    "                            visited.add(j)\n",
    "                            q.append([j, v * valueList[(i, j)]])\n",
    "                res.append(cur)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        edge = collections.defaultdict(list)\n",
    "        s = {}\n",
    "        for (i, j), v in zip(equations, values):\n",
    "            edge[i].append(j)\n",
    "            edge[j].append(i)\n",
    "            s[i+'/'+j] = v\n",
    "            s[j+'/'+i] = 1/v\n",
    "        \n",
    "        ans = []\n",
    "        for i, j in queries:\n",
    "            visited = set([i])\n",
    "            d = collections.deque([(i,1)])\n",
    "            while d:\n",
    "                cur, factor = d.popleft()\n",
    "                if j in edge[cur]:\n",
    "                    ans.append(factor*s[cur+'/'+j])\n",
    "                    break\n",
    "                else:\n",
    "                    for tmp in edge[cur]:\n",
    "                        if tmp not in visited:\n",
    "                            d.append((tmp,factor*s[cur+'/'+tmp]))\n",
    "                            visited.add(tmp)\n",
    "            else:\n",
    "                ans.append(-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import  List\n",
    "import collections\n",
    "class Solution:\n",
    "\n",
    "    def for_index(self,x:str,sum:int,flag:str,data:set) -> int :\n",
    "        if(x==flag):\n",
    "            return sum\n",
    "        for nex in self.data[x]:\n",
    "            if(nex[0] not in data):\n",
    "                data.add(nex[0])\n",
    "                su=self.for_index(nex[0],sum*nex[1],flag,data)\n",
    "                if su!=-1:\n",
    "                    return su\n",
    "        return  -1\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        self.data=collections.defaultdict(list)\n",
    "        self.data_set=set()\n",
    "        for i,(x,y) in enumerate(equations):\n",
    "            #将数据添加进入\n",
    "            self.data[x].append((y,values[i]))\n",
    "            self.data[y].append(((x,1/values[i])))\n",
    "            self.data_set.add(x)\n",
    "            self.data_set.add(y)\n",
    "        data_list=[]\n",
    "\n",
    "        for i,(x,y) in enumerate(queries):\n",
    "            q = collections.deque([(x,1)])\n",
    "            if(x not in self.data_set)or(y not in self.data_set):\n",
    "                data_list.append(-1)\n",
    "                continue\n",
    "            if(x==y):\n",
    "                data_list.append(1.0)\n",
    "            else:\n",
    "                data = set()\n",
    "                data_list.append(self.for_index(x,1,y,data))\n",
    "        return (data_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations, values, queries):\n",
    "        dic={}\n",
    "        self.makearr(equations,values,dic)\n",
    "        res=[]\n",
    "        for item in queries:\n",
    "            res.append(self.findres(item[0],item[1],dic))\n",
    "        return res\n",
    "    def makearr(self,equations,values,dic):\n",
    "        for index,item in enumerate(equations):\n",
    "            if item[0] not in dic:\n",
    "                dic[item[0]]={}\n",
    "            dic[item[0]][item[1]]=values[index]\n",
    "            if item[1] not in dic:\n",
    "                dic[item[1]]={}\n",
    "            dic[item[1]][item[0]]=1/values[index]\n",
    "\n",
    "    def findres(self,item0,item1,dic):\n",
    "        which = {}\n",
    "        for i in dic:\n",
    "            which[i] = -1\n",
    "        if item0 not in which or item1 not in which:\n",
    "            return -1.0\n",
    "        which[item0]=1\n",
    "        lis=[]\n",
    "        lis.append(item0)\n",
    "        while len(lis):\n",
    "            now=lis.pop()\n",
    "            for i in dic[now]:\n",
    "                if which[i]==-1:\n",
    "                    which[i]=which[now]/dic[now][i]\n",
    "                    lis.append(i)\n",
    "                if i==item1:\n",
    "                    return 1/which[i]\n",
    "        return -1.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        edge = collections.defaultdict(set)\n",
    "        s = {}\n",
    "        for (i, j), v in zip(equations, values):\n",
    "            edge[i].add(j)\n",
    "            edge[j].add(i)\n",
    "            s[i+'/'+j] = v\n",
    "            s[j+'/'+i] = 1/v\n",
    "        \n",
    "        ans = []\n",
    "        for i, j in queries:\n",
    "            visited = set([i])\n",
    "            d = collections.deque([(i,1)])\n",
    "            while d:\n",
    "                cur, factor = d.popleft()\n",
    "                if j in edge[cur]:\n",
    "                    ans.append(factor*s[cur+'/'+j])\n",
    "                    break\n",
    "                else:\n",
    "                    for tmp in edge[cur]:\n",
    "                        if tmp not in visited:\n",
    "                            d.append((tmp,factor*s[cur+'/'+tmp]))\n",
    "                            visited.add(tmp)\n",
    "            else:\n",
    "                ans.append(-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = defaultdict(dict)\n",
    "        \n",
    "        # Build the graph\n",
    "        for (x, y), val in zip(equations, values):\n",
    "            graph[x][y] = val\n",
    "            graph[y][x] = 1.0 / val\n",
    "        \n",
    "        # DFS function to find path weight\n",
    "        def dfs(start, end, visited):\n",
    "            # If the end node is in the graph of start node, return the weight\n",
    "            if end in graph[start]:\n",
    "                return graph[start][end]\n",
    "            \n",
    "            # Mark the start node as visited\n",
    "            visited.add(start)\n",
    "            \n",
    "            # Recursively search for a path from start's neighbors to the end\n",
    "            for neighbor, val in graph[start].items():\n",
    "                if neighbor not in visited:\n",
    "                    temp = dfs(neighbor, end, visited)\n",
    "                    if temp != -1:\n",
    "                        return val * temp\n",
    "            \n",
    "            # If no path found, return -1\n",
    "            return -1\n",
    "        \n",
    "        # Iterate through the queries and compute the result\n",
    "        result = []\n",
    "        for x, y in queries:\n",
    "            if x not in graph or y not in graph:\n",
    "                result.append(-1.0)\n",
    "            else:\n",
    "                result.append(dfs(x, y, set()))\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        kv = {}\n",
    "        for param1, param2 in equations:\n",
    "            if param1 not in kv:\n",
    "                kv[param1] = len(kv)\n",
    "            if param2 not in kv:\n",
    "                kv[param2] = len(kv)\n",
    "        n = len(kv)\n",
    "        graph = [[-1]*i+[1]+[-1]*(n-i-1) for i in range(n)]\n",
    "        for (param1, param2), value in zip(equations, values):\n",
    "            idx1, idx2 = kv[param1], kv[param2]\n",
    "            graph[idx1][idx2] = value\n",
    "            graph[idx2][idx1] = 1/value\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if graph[i][k] == -1 or graph[k][j] == -1:\n",
    "                        continue\n",
    "                    graph[i][j] = graph[i][k]*graph[k][j]\n",
    "        res = []\n",
    "        for param1, param2 in queries:\n",
    "            if param1 not in kv or param2 not in kv :\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                res.append(graph[kv[param1]][kv[param2]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = build_graph(equations, values)\n",
    "        results = []\n",
    "        \n",
    "        for i in range(len(queries)):\n",
    "            fr = queries[i][0]\n",
    "            to = queries[i][1]\n",
    "            if fr not in graph or to not in graph:\n",
    "                results.append(-1)\n",
    "            else:\n",
    "                visted = set()\n",
    "                results.append(dfs(graph, fr, to, visted))\n",
    "        return results\n",
    "\n",
    "def build_graph(equations, values):\n",
    "    graph = {}\n",
    "    for i in range(len(equations)):\n",
    "        v1 = equations[i][0]\n",
    "        v2 = equations[i][1]\n",
    "\n",
    "        if v1 not in graph:\n",
    "            graph[v1] = {}\n",
    "        graph[v1][v2] = values[i]\n",
    "\n",
    "        if v2 not in graph:\n",
    "            graph[v2] = {}\n",
    "        graph[v2][v1] = 1 / values[i]\n",
    "    return graph\n",
    "\n",
    "def dfs(graph, fr, to, visted):\n",
    "    if fr == to:\n",
    "        return 1\n",
    "    visted.add(fr)\n",
    "    for k, v in graph[fr].items():\n",
    "        if k not in visted:\n",
    "            next_val = dfs(graph, k, to, visted)\n",
    "            if next_val >= 0:\n",
    "                return v * next_val\n",
    "    visted.remove(fr)\n",
    "    return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        dic1,vis={},{}\n",
    "        def dic_add(k,v,val):\n",
    "            if k not in dic1:\n",
    "                dic1[k]=[[v,val]]\n",
    "            else:\n",
    "                dic1[k].append([v,val])\n",
    "        for idx,(f,t) in enumerate(equations) :\n",
    "            dic_add(f,t,values[idx])\n",
    "            dic_add(t,f,1/values[idx])\n",
    "            vis[t]=False\n",
    "            vis[f]=False\n",
    "        res=[]\n",
    "        def dfs(f,t,cur_v):\n",
    "            if f not in dic1:return -1\n",
    "            if f==t:return cur_v\n",
    "            for i,val in dic1[f]:\n",
    "                if not vis[i]:\n",
    "                    vis[i]=True\n",
    "                    ans=dfs(i,t,cur_v*val)\n",
    "                    vis[i]=False    \n",
    "                    if  ans!=-1:\n",
    "                        return ans \n",
    "            return -1\n",
    "        for idx,(f,t) in enumerate(queries):\n",
    "            vis[f]=True\n",
    "            res.append(dfs(f,t,1))\n",
    "            vis[f]=False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        self.data=collections.defaultdict(list)\n",
    "        self.data_set=set()\n",
    "        for i,(x,y) in enumerate(equations):\n",
    "            #将数据添加进入\n",
    "            self.data[x].append((y,values[i]))\n",
    "            self.data[y].append(((x,1/values[i])))\n",
    "            self.data_set.add(x)\n",
    "            self.data_set.add(y)\n",
    "        print(self.data)\n",
    "        data_list=[]\n",
    "\n",
    "        for i,(x,y) in enumerate(queries):\n",
    "            q = collections.deque([(x,1)])\n",
    "            if(x not in self.data_set)or(y not in self.data_set):\n",
    "                data_list.append(-1)\n",
    "                continue\n",
    "            if(x==y):\n",
    "                data_list.append(1.0)\n",
    "            else:\n",
    "                data = set()\n",
    "                while 1:\n",
    "                    if not q:\n",
    "                        data_list.append(-1)\n",
    "                        break\n",
    "                    (key,value)=q.pop()\n",
    "                    if(key==y):\n",
    "                        data_list.append(value)\n",
    "                        break\n",
    "                    for nex in self.data[key]:\n",
    "       \n",
    "                        if nex[0] not in data:\n",
    "                            data.add(nex[0])\n",
    "                            q.append((nex[0],value*nex[1]))\n",
    "        return data_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import collections\n",
    "#\n",
    "#\n",
    "# class Solution:\n",
    "#     def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "#         graph = collections.defaultdict(list)\n",
    "#         node = set()  # 统计节点\n",
    "#         for i, (x, y) in enumerate(equations):  # 构建图\n",
    "#             graph[x].append((y, values[i]))\n",
    "#             graph[y].append((x, 1 / values[i]))\n",
    "#             node.add(x)\n",
    "#             node.add(y)\n",
    "#         res = []\n",
    "#         visited = {x: False for x in node}  # 访问过的节点，避免死循环\n",
    "#         # 求解\n",
    "#         for x, y in queries:\n",
    "#             if (x not in node) or (y not in node):  # 节点没出现过，直接返回-1\n",
    "#                 res.append(-1)\n",
    "#                 continue\n",
    "#             visited[x] = True\n",
    "#             ans = self.dfs(graph, x, y, 1, visited)  # DFS返回答案\n",
    "#             visited[x] = False\n",
    "#             res.append(ans)\n",
    "#         return res\n",
    "#\n",
    "#     def dfs(self, graph, x, target, temp, visited):\n",
    "#         if x == target:  # 找到目标, 返回答案\n",
    "#             return temp\n",
    "#         for next_item in graph[x]:  # 下一个节点\n",
    "#             next_node, weight = next_item\n",
    "#             if not visited[next_node]:\n",
    "#                 visited[next_node] = True\n",
    "#                 res = self.dfs(graph, next_node, target, temp * weight, visited)\n",
    "#                 visited[next_node] = False\n",
    "#                 if res != -1:  # 找到答案了直接返回，否者继续DFS\n",
    "#                     return res\n",
    "#         return -1\n",
    "#\n",
    "#\n",
    "from typing import  List\n",
    "import collections\n",
    "class Solution:\n",
    "\n",
    "    def for_index(self,x:str,sum:int,flag:str,data:set) -> int :\n",
    "        if(x==flag):\n",
    "            return sum\n",
    "        for nex in self.data[x]:\n",
    "            if(nex[0] not in data):\n",
    "                data.add(nex[0])\n",
    "\n",
    "                su=self.for_index(nex[0],sum*nex[1],flag,data)\n",
    "                if su!=-1:\n",
    "                    return su\n",
    "        return  -1\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        self.data=collections.defaultdict(list)\n",
    "        self.data_set=set()\n",
    "        for i,(x,y) in enumerate(equations):\n",
    "            #将数据添加进入\n",
    "            self.data[x].append((y,values[i]))\n",
    "            self.data[y].append(((x,1/values[i])))\n",
    "            self.data_set.add(x)\n",
    "            self.data_set.add(y)\n",
    "        data_list=[]\n",
    "\n",
    "        for i,(x,y) in enumerate(queries):\n",
    "            q = collections.deque([(x,1)])\n",
    "            if(x not in self.data_set)or(y not in self.data_set):\n",
    "                data_list.append(-1)\n",
    "                continue\n",
    "            if(x==y):\n",
    "                data_list.append(1.0)\n",
    "            else:\n",
    "                data = set()\n",
    "                data_list.append(self.for_index(x,1,y,data))\n",
    "                # while 1:\n",
    "                #     (key,value)=q.pop()\n",
    "                #     if not q:\n",
    "                #         data_list.append(-1)\n",
    "                #         break\n",
    "                #     if(key==y):\n",
    "                #         data_list.append(value)\n",
    "                #         break\n",
    "                #     for nex in self.data[key]:\n",
    "                #         if nex[0] not in data:\n",
    "                #             data.add(nex[0])\n",
    "                #             q.append((nex[0],value*nex[1]))\n",
    "\n",
    "        return (data_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        graph = {}\n",
    "        self.len = len(equations)\n",
    "        for i in range(self.len):\n",
    "            if not graph.get(equations[i][0]):\n",
    "                graph[equations[i][0]] = [(equations[i][1], values[i])]\n",
    "            else:\n",
    "                graph[equations[i][0]].append((equations[i][1], values[i]))\n",
    "            if not graph.get(equations[i][1]):\n",
    "                graph[equations[i][1]] = [(equations[i][0], 1./values[i])]\n",
    "            else:\n",
    "                graph[equations[i][1]].append((equations[i][0], 1./values[i]))\n",
    "        # print(graph)\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            num1, num2 = query[0], query[1]\n",
    "            if num1 not in graph or num2 not in graph:\n",
    "                res.append(-1.0)\n",
    "            else:\n",
    "                visited = set()\n",
    "                visited.add(num1)\n",
    "                res_temp = self.dfs(num1, num2, graph, visited)\n",
    "                res.append(res_temp)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def dfs(self, num1, num2, graph, visited):\n",
    "        if num1==num2:\n",
    "            return 1.0\n",
    "        for value in graph[num1]:\n",
    "            to, temp = value[0], value[1]\n",
    "            if to not in visited:\n",
    "                visited.add(to)\n",
    "                res_temp = self.dfs(to, num2, graph, visited)\n",
    "                if res_temp>0:\n",
    "                    return temp*res_temp\n",
    "        visited.remove(num1)\n",
    "        return -1.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        fa = {}\n",
    "        w = {}\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                t = fa[x]\n",
    "                fa[x] = find(fa[x])\n",
    "                w[x] *= w[t]\n",
    "            return fa[x]\n",
    "\n",
    "        def union(x,y,v):\n",
    "            fx,fy = find(x),find(y)\n",
    "            if fx != fy:\n",
    "                fa[fx] = fy\n",
    "                w[fx] = v * w[y] / w[x]\n",
    "\n",
    "        for [a,b],v in zip(equations,values):\n",
    "            if a not in fa:\n",
    "                fa[a] = a\n",
    "                w[a] = 1\n",
    "            if b not in fa:\n",
    "                fa[b] = b\n",
    "                w[b] = 1\n",
    "            union(a,b,v)\n",
    "        ans = []\n",
    "        for a,b in queries:\n",
    "            if a in fa and b in fa and find(a) == find(b):\n",
    "                ans.append(w[a] / w[b])\n",
    "            else:\n",
    "                ans.append(-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import  List\n",
    "import collections\n",
    "class Solution:\n",
    "\n",
    "    def for_index(self,x:str,sum:int,flag:str,data:set) -> int :\n",
    "        if(x==flag):\n",
    "            return sum\n",
    "        for nex in self.data[x]:\n",
    "            if(nex[0] not in data):\n",
    "                data.add(nex[0])\n",
    "                su=self.for_index(nex[0],sum*nex[1],flag,data)\n",
    "                if su!=-1:\n",
    "                    return su\n",
    "        return  -1\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        self.data=collections.defaultdict(list)\n",
    "        self.data_set=set()\n",
    "        for i,(x,y) in enumerate(equations):\n",
    "            #将数据添加进入\n",
    "            self.data[x].append((y,values[i]))\n",
    "            self.data[y].append(((x,1/values[i])))\n",
    "            self.data_set.add(x)\n",
    "            self.data_set.add(y)\n",
    "        data_list=[]\n",
    "\n",
    "        for i,(x,y) in enumerate(queries):\n",
    "            q = collections.deque([(x,1)])\n",
    "            if(x not in self.data_set)or(y not in self.data_set):\n",
    "                data_list.append(-1)\n",
    "                continue\n",
    "            if(x==y):\n",
    "                data_list.append(1.0)\n",
    "            else:\n",
    "                data = set()\n",
    "                data_list.append(self.for_index(x,1,y,data))\n",
    "        return (data_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        class union_finder:\n",
    "            def __init__(self, variables):\n",
    "                self.root = {v: (v, 1.0) for v in variables}\n",
    "                \n",
    "            def find(self, x, scale):\n",
    "                if x == self.root[x][0]:\n",
    "                    return x, 1 * scale\n",
    "                rootX, f_scale = self.find(self.root[x][0], self.root[x][1])\n",
    "\n",
    "                return rootX, scale * f_scale\n",
    "                        \n",
    "            def union(self, x, y, scale):\n",
    "                if scale < 1:\n",
    "                    y, x, scale = x, y, 1 / scale\n",
    "                \n",
    "                rootX, scale_x = self.find(x, 1)\n",
    "                rootY, scale_y = self.find(y, 1)\n",
    "\n",
    "                self.root[rootY] = rootX, scale_x * scale / scale_y\n",
    "\n",
    "        variables = []\n",
    "        for eq in equations:\n",
    "            variables.extend(eq)\n",
    "        variables = set(variables)\n",
    "        finder = union_finder(variables)\n",
    "\n",
    "        for eq, v in zip(equations, values):\n",
    "            A, B = eq\n",
    "            finder.union(A, B, v)\n",
    "            \n",
    "        ret = []\n",
    "        for C, D in queries:\n",
    "            if C not in variables or D not in variables:\n",
    "                ret.append(-1)\n",
    "                continue\n",
    "            rootC, scale_c = finder.find(C, 1)\n",
    "            rootD, scale_d = finder.find(D, 1)\n",
    "            if rootC != rootD:\n",
    "                ret.append(-1)\n",
    "            else:\n",
    "                ret.append(scale_d / scale_c)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        d = {}\n",
    "        p = {}\n",
    "        def myFind(i):\n",
    "            if i != p[i]:\n",
    "                p[i] = myFind(p[i])\n",
    "            return p[i]\n",
    "        def myUnion(i, j):\n",
    "            pi, pj = myFind(i), myFind(j)\n",
    "            p[pi] = pj\n",
    "            return\n",
    "\n",
    "        for e, v in zip(equations, values):\n",
    "            a, b = e[0], e[1]\n",
    "            if a not in d: \n",
    "                d[a] = {}\n",
    "                p[a] = a\n",
    "            if b not in d: \n",
    "                d[b] = {}\n",
    "                p[b] = b\n",
    "            myUnion(a, b)\n",
    "            d[a][b] = v\n",
    "            d[b][a] = 1.0 / v\n",
    "\n",
    "        val = {}\n",
    "        for k in d:\n",
    "            if k not in val:\n",
    "                val[k] = 1.0\n",
    "                q = deque([k])\n",
    "                while len(q) > 0:\n",
    "                    i = q.popleft()\n",
    "                    for j in d[i]:\n",
    "                        if j not in val:\n",
    "                            val[j] = val[i] / d[i][j]\n",
    "                            q.append(j)\n",
    "        ans = []\n",
    "        for ci, di in queries:\n",
    "            if ci not in val or di not in val or myFind(ci) != myFind(di):\n",
    "                ans.append(-1.0)\n",
    "            else:\n",
    "                ans.append(val[ci] / val[di])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float],\n",
    "                     queries: List[List[str]]) -> List[float]:\n",
    "        h = dict()\n",
    "        nexts = DefaultDict(set)\n",
    "        for (a, b), v in zip(equations, values):\n",
    "            nexts[a].add(b)\n",
    "            h[(a, b)] = v\n",
    "            nexts[b].add(a)\n",
    "            h[(b, a)] = 1 / v\n",
    "\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            if a not in nexts or b not in nexts:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                visit = set()\n",
    "                visit.add(a)\n",
    "                q = deque([(a,1)])\n",
    "                cur = -1\n",
    "                while q:\n",
    "                    p,v = q.pop()\n",
    "                    if p == b:\n",
    "                        cur = v\n",
    "                        break\n",
    "                    for next in nexts[p]:\n",
    "                        if next not in visit:\n",
    "                            visit.add(next)\n",
    "                            q.append((next,v*h[(p,next)]))\n",
    "                ans.append(cur)\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        id = dict()\n",
    "        for a, b in equations:\n",
    "            if a not in id:\n",
    "                id[a] = len(id)\n",
    "            if b not in id:\n",
    "                id[b] = len(id)\n",
    "        fa = list(range(len(id)))\n",
    "        w = [1] * len(id)\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                f = find(fa[x])\n",
    "                w[x] *= w[fa[x]]\n",
    "                fa[x] = f\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(x: int, y: int, v: float):\n",
    "            fx, fy = find(x), find(y)\n",
    "            w[fx] = w[y] / w[x] * v\n",
    "            fa[fx] = fy\n",
    "        \n",
    "        for (a, b), v in zip(equations, values):\n",
    "            merge(id[a], id[b], v)\n",
    "\n",
    "        ans = [-1.0] * len(queries)\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if a not in id or b not in id or find(id[a]) != find(id[b]):\n",
    "                continue\n",
    "            ans[i] = w[id[a]] / w[id[b]]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        dic1,vis={},{}\n",
    "        def dic_add(k,v,val):\n",
    "            if k not in dic1:\n",
    "                dic1[k]=[[v,val]]\n",
    "            else:\n",
    "                dic1[k].append([v,val])\n",
    "        for idx,(f,t) in enumerate(equations) :\n",
    "            dic_add(f,t,values[idx])\n",
    "            dic_add(t,f,1/values[idx])\n",
    "            vis[t]=False\n",
    "            vis[f]=False\n",
    "        res=[]\n",
    "        def dfs(f,t,cur_v):\n",
    "            if f not in dic1:return -1\n",
    "            if f==t:return cur_v\n",
    "            for i,val in dic1[f]:\n",
    "                if not vis[i]:\n",
    "                    vis[i]=True\n",
    "                    ans=dfs(i,t,cur_v*val)\n",
    "                    vis[i]=False    \n",
    "                    if  ans!=-1:\n",
    "                        return ans \n",
    "            return -1\n",
    "        for idx,(f,t) in enumerate(queries):\n",
    "            res.append(dfs(f,t,1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        g = defaultdict(list)\n",
    "        for (u, v), w in zip(equations, values):\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, 1 / w))\n",
    "\n",
    "        def dfs(u, cur, end, i):\n",
    "            vis.add(u)\n",
    "            if u == end:\n",
    "                ans[i] = cur\n",
    "            for v, w in g[u]:\n",
    "                if v not in vis:\n",
    "                    dfs(v, cur * w, end, i)\n",
    "\n",
    "        ans = [-1.0] * len(queries)\n",
    "        for i, (u, v) in enumerate(queries):\n",
    "            if u not in g or v not in g: continue\n",
    "            vis = set()\n",
    "            dfs(u, 1.0, v, i)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
